#include<iostream>
#include<assert.h>
#include<string.h>

using std::cout;
using std::cin;
using std::endl;

//template<class T>
template<typename T>
class Stack
{
public:
  // 构造函数
  Stack(int capacity = 0)
    :_a(NULL)
    ,_size(0)
    ,_capacity(0)
  {
    // 防止负数的传入
    if (capacity > 0)
    {
      _a = new T[capacity];
      _capacity = capacity;
    }
  }
  // 析构函数
  ~Stack()
  {
    delete[] _a;
    _a = NULL;
    _size = _capacity = 0;
  }
  // 拷贝构造
  Stack(const Stack& s)
    :_a(NULL)
    ,_size(s._size)
    ,_capacity(s._capacity)
  {
    _a = new T[_capacity];
    memcpy(_a, s._a, sizeof(T) * _size);
  }

  // 插入数据 入栈
  void push(const T& val)
  {
    if (_size == _capacity)
    {
      int newcapacity = _capacity == 0 ? 4 : _capacity * 2;
      T* tmp = new T[newcapacity];
      // 空的就不用插入了
      if (_a)
      {
        memcpy(tmp, _a, sizeof(T) * _size);
        delete[] _a;
      }
      _a = tmp;
      _capacity = newcapacity;  
    }
    _a[_size++] = val;
  }

  // 出数据 先进后出，后进先出
  const T& top()
  {
    assert(!empty());
    return _a[_size - 1];
  }

  void pop()
  {
    assert(!empty());
    _size--;
  }

  bool empty()
  {
    return _size == 0;
  }

private:
  T* _a;
  int _size;
  int _capacity;
};

